"""
Copyright 2009, Thomas Dejanovic, Jay Shurtz.
 
This is free software; you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License as
published by the Free Software Foundation; either version 2.1 of
the License, or (at your option) any later version.

This software is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this software; if not, write to the Free
Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
02110-1301 USA, or see the FSF site: http://www.fsf.org.
"""

id = "$Id: hatch_address_mapper.py 667 2010-07-01 00:12:17Z jayshurtz $"
# $URL: http://hatch.googlecode.com/svn/tags/taggle_release_2.2/hatch/hatch_visitors/hatch_address_mapper.py $
# $Author: jayshurtz $
version = " ".join(id.split()[1:3])


import to_hatch_structure
from hatch_visitor import *
from hatch_register import Register # TODO - Remove this. Visitor should work with properties, not class types.
from hatch_struct import Pack

from hatch_constants import BIT_WIDTH
from hatch_constants import DATA_BUS_WIDTH  # TODO - this is a hack, this value is a function of the target bus and should be passed in in some way.

#TOP_OF_MEMORY    = 0xffffffff   # TODO - Move to hatch_constants.py ?
#BOTTOM_OF_MEMORY = 0x0


    # TODO - invalidate the address_width property if a new child is added ?
    # TODO - check locked_address, etc (see addressMapper) ?

# TODO - use 'bits_to_address' vs 'address_range'

    # TODO - lock_local_address_map, lock_global_address_map (hatch_node class to use these ?)
    # TODO If a childNode is added or removed, after visiting, remove the 'bit_width' & address_width properties ? (not here, in class)
    # TODO - check that self.property('address_range') is big enough to address all registers in this struct. (It may have been manually specified.)
    # XXX - probably not manually set: check that baseAddr isn't outside of a preset address width ?

    # bit_width, base_bit
    # address_width, address_local, address_global

        #if hatchNode.properties['lock_address']:
        #    raise AssertionError, hatchNode.__class__.__name__ + " '" + hatchNode.name + "' already has a locked local base address of " + str(hex(XXX)) + "."


# TODO - thomasd : clearly define and apply local and globa address
# scopes and applications.

# TODO - get rid of packs.


class Hatch_Address_Mapper(HatchVisitor):
    """ Class for setting the address-related properties of a hatch node.

        This is a 2 step process.  first set the register width and
        pack registers into packs.  Then ?

        Currently this class works on a generic level by using node
        properties rather than specific classes.  This class
        implements all the address-related methods that would
        otherwise be needed by the hatch node classes themselves.
    """
    def visit_function(self, hatchNode):
        """ 
        """

        # this is a list of pairs of values defining an address range.
        # ranges should not overlap.
        self._free_block_list = [[0, -1]]

        self._visit_function_recurse_first_pass(hatchNode)

        bottom = self._free_block_list[0]
        
        # nail down the top node.
        if (bottom[1] >= 0):
            hatchNode.properties['base_address']  = bottom[1]+1
        else:
            hatchNode.properties['base_address']  = hatchNode.properties['local_address']

        hatchNode.properties['address_range'] = hatchNode.properties['local_address_range']

        self._visit_function_recurse_second_pass(hatchNode)


    def _visit_function_recurse_first_pass(self, hatchNode):
        """
        """
        self._set_bit_width(hatchNode)     # set the bit width of this node.
        for c in hatchNode.childNodes:  # Recurse into child Nodes.
            self._visit_function_recurse_first_pass(c)
        self._set_local_address(hatchNode) # set address for each element in the scope of it's parent.

        # check if this node has a user defined address.  if it does
        # then slice it out of the available memory block list.
        a_value = hatchNode.properties.get('address', '')
        a_width = self._get_address_width(hatchNode)

        if a_value != '' :
            foundFreeSpace = False
            for aRange in self._free_block_list:
                if (aRange[0] <= a_value) and ((aRange[1] >= a_value) or (aRange[1] == -1)):
                    # we are inside the address range, make a hole in it for this node if it fits.
                    if ((aRange[1] < (a_value + a_width)) and (aRange[1] != -1)) :
                        # this free block is not big enaugh to fit this node.
                        raise AssertionError, "Could not fit node "+str(hatchNode)+ " into address space as the free block was too small "+str(self._free_block_list)
                    foundFreeSpace = True
                    if (aRange[0] == a_value):
                        aRange[0] = a_value + a_width
                    elif (aRange[1] == a_value):
                        # the range check above implies this can only be one location in size.
                        aRange[1] = a_value - 1
                    else:
                        bRange = [a_value + a_width, aRange[1]]
                        aRange[1] = a_value - 1;
                        self._free_block_list.append(bRange)
                    break
            if not foundFreeSpace:
                raise AssertionError, "Could not fit "+str(hatchNode)+ " into address space as there was no free space "+str(self._free_block_list)


    def _visit_function_recurse_second_pass(self, hatchNode):

        """ this assigns an address to everything assuming it can find an
            address in the free block list to fit the node.  If the
            node has a user defined addres then that is used and it is
            assumed that the block has already been carved out of the
            free block list in the first pass.
        """
        ba = hatchNode.properties.get('address', hatchNode.properties['base_address'])
        for c in hatchNode.childNodes:  # Recurse into child Nodes.
            c.properties['base_address']  = c.properties.get('address', ba)
            c.properties['address_range'] = c.properties['local_address_range']
            if hatchNode.__class__.__name__ != Pack.__name__:
                ba += c.properties['address_range']
            self._visit_function_recurse_second_pass(c)

    def _set_bit_width(self, hatchNode): # This function is not really needed for this mapper.
        """ figure out the width of this node.  Don't check, just set it.

            if hatchNode is a register the width is what it is. if it
            is not in a pack, default the base bit to 0, otherwise let
            the pack set it.

            if hatchNode is a register pack the width is just the sum
            of all it's registers.  dont check if the width is wider
            than the bus because we don't know what the bus width is
            yet

            we have no business calculating the bit width of anything else.
        """


        # XXX Instead of using class, use node properties.
        # This way the logic still works for any classes that INHERIT from these.
        # example:  Register has node.properties['hatch_leaf'] == True.

        if hatchNode.__class__.__name__ == Register.__name__:
            # hatchNode is a register so the width is what it is.
            # if we are not in a pack, default the base bit to 0,
            # otherwise let the pack set it.
            if hatchNode.parent.__class__.__name__ != Pack.__name__:
                # we do this test here so it does not matter if this
                # method is called top down or bottom up.
                hatchNode.properties['base_bit'] = 0
                hatchNode.properties['packed'] = False
        elif hatchNode.__class__.__name__ == Pack.__name__:
            # hatchNode is a register pack so the width is just the
            # sum of all it's registers.  dont check if the width is
            # wider than the bus because we don't know what the bus
            # width is yet.
            width = 0
            hatchNode.properties['base_bit'] = 0
            packedChildren = len(hatchNode.childNodes) > 1
            for ci in range(len(hatchNode.childNodes)-1, -1, -1): 
                c = hatchNode.childNodes[ci]
                try:
                    c.properties['base_bit'] = width
                    width += c.properties['bit_width']
                    c.properties['packed'] = packedChildren
                except KeyError, e:
                    raise AssertionError, "It appears that "+str(c)+ " in " + str(self) + " does not have a register width defined."
            
            hatchNode.properties['bit_width'] = width
        else:
            # we have no business calculating the bit width of anything else.
            hatchNode.properties['packed'] = False

    def _set_local_address(self, hatchNode):
        """ Figure out how wide everything is and set a local address for all
            children in the scope of any parent class.

            TODO - respect the address of nodes to make them fixed in
            the address space.
        """
        if (hatchNode.__class__.__name__ == Pack.__name__) or (hatchNode.__class__.__name__ == Register.__name__):
            hatchNode.properties['local_address_range'] = 1
            hatchNode.properties['local_address'] = 0
        else:
            range = 0
            for c in hatchNode.childNodes: 
                c.properties['local_address'] = range
                range += c.properties['local_address_range']
            if range == 0:
                raise AssertionError, "Calculated address range for %s is zero, this implies an empty node."%(hatchNode.name)

            hatchNode.properties['local_address_range'] = range
            hatchNode.properties['local_address'] = 0


    def _get_address_width(self, hatchNode):
        """ Get the number of address locations taken up by this hatch
            node. If the address width property is not set, set it.
        """

        if (hatchNode.__class__.__name__ == Register.__name__ ) or \
                (hatchNode.__class__.__name__ == Pack.__name__):
            # by definition.
            hatchNode.properties['address_width'] = 1
        else:
            addressWidth = hatchNode.properties.get('address_width', 0)
            if addressWidth == 0:
                # we need to set it.
                for c in hatchNode.childNodes:
                    addressWidth += self._get_address_width(c)
            hatchNode.properties['address_width'] = addressWidth
        return  hatchNode.properties['address_width']










    # Legacy style functions.
    if False:
        def elaborate (self):
            """ Run any functions needed to flesh out data structures as a
                prelude to generating anything.
            """
            for c in self.contentList:
                c.elaborate()
            # now find the address blocks.
            fixedBlockList = []
            movableBlockList = []
            for c in self.contentList:
                addrRange = c.get_address_range()
                baseAddr = c.get_base_address()
                decodeBits = int(math.ceil(math.log(addrRange) / math.log(2)))
                addrRange = (2L ** decodeBits)
                mask = addrRange - 1L
                if (baseAddr & mask) != 0:
                    raise """*** ERROR - the base address 0x%x for %s is not alligned correctly for the
                    address mask generated 0x%x."""%(baseAddr, c.name, mask)
                if baseAddr == 0:
                    movableBlockList.append([baseAddr, addrRange, c])
                else :
                    fixedBlockList.append([baseAddr, addrRange, c])
            # now go through the movable blocks and sort them by size
            _sort_block_list_by_size_(movableBlockList)
            # OK, now pack the movable blocks into the free spaces.  Use
            # the smallest spaces first and then pack stuff above any
            # predefined blocks.
            # simple pack.  There is some polishing that could be done
            # here, but simple gets it done in finite time :-)
            for b, r, c in movableBlockList:
                # find any free space between fixed blocks.
                _free_block_list = _build_free_block_list_(fixedBlockList)
                # get a free block big enaugh to fit the current movable block.
                baseAddr = _get_base_addre_of_space_(_free_block_list, r)
                fixedBlockList.append([baseAddr, r, c])
            # go through and update the base address in all the fixed blocks.
            for b, r, c in fixedBlockList:
                c.set_base_address(b)
                print "updated base address of", c.name, "to 0x%x"%(b)
            for b, r, c in fixedBlockList:
                x = c.get_base_address()
                print "double checkeing base address of", c.name, "is 0x%x, should be 0x%x"%(x, b)
            # store the range and base for this mux for handy access by
            # other levels in the tree.
            _sort_block_list_by_base_(fixedBlockList)
            baseAddr = fixedBlockList[-1][0]
            # range is the highest block + it's range - our base.
            addrRange =fixedBlockList[0][0] + fixedBlockList[0][1] - baseAddr
            self.set_property('base_address', baseAddr)
            self.set_property('address_range', addrRange)
            self.property('target_bus').elaborate()
        def get_base_address (self):
            """ Return the base address for this register block."""
            if self.has_property('base_address'):
                return self.property('base_address')
            else:
                return 0L
        def get_address_range (self, addrBase=0):
            """ Return the number of locations required for this apb slave mux."""
            if not self.has_property('address_range'):
                self.elaborate()
            return self.property('address_range')
    if False:
        def get_base_address (self):
            """return the base address for this register block."""
            if not self.has_property('base_address'):
                self.set_property('base_address', self.hatchling.get_base_address())
            return self.property('base_address')
        def set_base_address (self, baseAddr):
            """set the base address for this register block."""
            self.set_property('base_address', baseAddr)
        def get_address_range (self):
            """return the number of locations required for this block."""
            return self.hatchling.get_address_range()


class Hatch_Address_Mapper_Packed(Hatch_Address_Mapper):
    """ Set the bit-related properties of a hatch node in an optimal way.
        Hatch nodes that can be packed bitwise into a single data bus address are packed.
        This class is different from a plain address mapper in two ways, it checks if
        hatchNodes can be packed bit-wise into memory, and it packs them where possible.
    """
    def visit_function(self, hatchNode):
        """ """
        self.visit_function_recurse(hatchNode, False, 0, 0, 0) # Defaults to quick (not forced) at base addr of 0.
        self._set_bit_width(hatchNode, False)   # Get bit width of hatchNode too (otherwise starts with childNodes.)
        self._get_address_width(hatchNode, False)   # Get all address width of hatchNode too (otherwise starts with childNodes.)
        #self.get_packable(hatchNode, False)
        self.deleteTemporaryProperties(hatchNode, ['packable_bits'])   # Done visiting, delete temporary properties.

    def visit_function_recurse(self, hatchNode, forceCheck=False, addressLocal=0, addressGlobal=0, bitGlobal=0):
        """ """
        #logger.debug(self.visit_function_recurse.func_name + "(" + hatchNodeClassAndName(hatchNode) + ")")
        newBitGlobal, newAddressGlobal, nextFreeBitGlobal, nextFreeAddressGlobal = self.pack_bits(hatchNode, forceCheck, bitGlobal, addressGlobal)
        addressLocal += newAddressGlobal-addressGlobal  # Adjust 'local' address based on changes to global address.
        #logger.debug('Args   addressLocal, addressGlobal, bitGlobal = ' + str(addressLocal) + ", " + str(addressGlobal) + ", " + str(bitGlobal))
        #logger.debug('Packed addressLocal, addressGlobal, bitGlobal = ' + str(addressLocal) + ", " + str(newAddressGlobal) + ", " + str(newBitGlobal))
        #logger.debug('Calc   nextFreeBitGlobal, nextFreeAddressGlobal = ' + str(nextFreeBitGlobal) + ", " + str(nextFreeAddressGlobal))
        self.set_map(hatchNode, addressLocal, newAddressGlobal, newBitGlobal) # Put in memory.
        #if len(hatchNode.childNodes) > 0:
        #    logger.debug('Looping through child nodes ' + str([str(c) for c in hatchNode.childNodes]))
        childBitGlobal, childAddressGlobal = newBitGlobal, newAddressGlobal # Use corrected 'packed' values.
        childAddressLocal = 0  # Local address of child nodes is relative to this node.
        for c in hatchNode.childNodes:  # Recurse into child Nodes.
            childNextFreeBitGlobal, childNextFreeAddressGlobal = self.visit_function_recurse(c, \
                forceCheck, childAddressLocal, childAddressGlobal, childBitGlobal)
            childAddressLocal += childNextFreeAddressGlobal-childAddressGlobal  # Adjust 'local' address based on changes to global address.
            childBitGlobal, childAddressGlobal = childNextFreeBitGlobal, childNextFreeAddressGlobal # Increment for next iteration.
        return nextFreeBitGlobal, nextFreeAddressGlobal

    def get_packable(self, hatchNode, forceCheck=False):
        """ A hatch node is 'packable' (can be packed bit-wise into a single address) 
            if and only if it is 'packed,' does not contain any un-packable nodes, 
            AND is small enough to fit into a single address.

            Size is checked by accumulating bits from the lowest nodes only until all bits 
            are accumulated or a limit is exceeded.  This is usually used to check if 
            the total bit width (or width in bits) is greater than the data bus width.
            This should be faster than calling '_set_bit_width'.
            A node *can* be 'packed' without being 'packable.'
        """
        #logger.debug(self.get_packable.func_name + "(" + hatchNodeClassAndName(hatchNode) + ")")
        packable = True
        accumulatedBits = 0
        errored = False
        if not forceCheck:
            try:
                packable = hatchNode.properties['packable']
                accumulatedBits = hatchNode.properties['packable_bits']    # Width is also needed by any parent node.
                #logger.debug('packable already set to ' + str(packable) + ".")
            except KeyError, e:
                errored = True
        if forceCheck or errored:
            if not hatchNode.properties['packed']:
                packable = False    # Is not packed, therefore is not packable.
                #logger.debug('not packed!')
            elif len(hatchNode.childNodes) == 0:    # This node is packed & is a leaf.
                #logger.debug('checking bit width...')
                accumulatedBits = hatchNode.properties['bit_width']
                if accumulatedBits > DATA_BUS_WIDTH:
                    #logger.debug('childless node too wide!')
                    packable = False
            else:   # This node is packed & is a block.
                #logger.debug('going for child nodes...')
                accumulatedBits = 0
                for c in hatchNode.childNodes:
                    childPackable, childBits = self.get_packable(c, forceCheck)
                    accumulatedBits += childBits
                    if not childPackable:
                        #logger.debug('child returned unpackable!')
                        packable = False    # A child node is not packable, therefore this node is not either.
                        break
                    if accumulatedBits > DATA_BUS_WIDTH:
                        #logger.debug('accumulated too many bits: ' + str(accumulatedBits))
                        packable = False    # This node is too many bits.
                        break
        hatchNode.properties['packable'] = packable # Set property.
        hatchNode.properties['packable_bits'] = accumulatedBits # Set property.
        return packable, accumulatedBits  # For convenience.

    def _set_bit_width(self, hatchNode, forceCheck=False):
        """ Get the width in bits of a hatch node. If the bit width property is not set, set it.
            This class does pack bits, so all bits are counted.
        """
        bitWidth = 0
        errored = False
        if not forceCheck:
            try:
                bitWidth = hatchNode.properties['bit_width']    # Get if already set, forceCheck stays False.
            except KeyError, e:
                errored = True   # Not already set, force a check.
        if forceCheck or errored:
            if len(hatchNode.childNodes) == 0:
                bitWidth = hatchNode.properties['bit_width']  # This is a stored property that cannot be generated from childNodes. Raise error if not set.
            else:
                for c in hatchNode.childNodes:
                    bitWidth += self._set_bit_width(c, forceCheck)   # No shortcuts based on DATA_BUS_WIDTH, return actual width in bits.
                hatchNode.properties['bit_width'] = bitWidth    # Set property.
        return bitWidth # Return property as a convenience. 

    def _get_address_width(self, hatchNode, forceCheck=False, baseBit=0):
        """ Get the width in addresses of a hatch node. If the address width property is not set, set it.
            This class packs bits, so the address width may be affected by how well items can be packed,
            which itself is affected by the hatchNode baseBit (which affects where address wrapping can happen.)
            The address width when packed is not necessarily equal to the sum of all child node address widths.
        """
        #logger.debug(self._get_address_width.func_name + "(" + hatchNodeClassAndName(hatchNode) + ")")
        addressWidth = 0
        errored = False
        if not forceCheck:
            try:
                addressWidth = hatchNode.properties['address_width']    # Get if already set, forceCheck stays False.
                #logger.debug('address width already set to ' + str(addressWidth) + ".")
            except KeyError, e:
                errored = True   # Not already set, force a check.
        if forceCheck or errored:
            if len(hatchNode.childNodes) == 0:
                addressWidth = 1    # Lowest-level nodes cannot wrap, must be < DATA_BUS_WIDTH in bits, and fit into a single address.
                if hatchNode.properties['bit_width'] == 0:
                    addressWidth = 0    # If node occupies zero bits, it occupies 0 addresses as well.
                #logger.debug('leaf node, address width forced to ' + hex(addressWidth))
            else:
                occupiesZeroBits = True
                baseAddress = 0 # We're only interested in width here, so start at 0.
                baseBitNew = baseBit
                baseAddressNew = baseAddress
                for c in hatchNode.childNodes:  # Pack everything in.
                    baseBitNew, baseAddressNew, nextFreeBit, nextFreeAddress = self.pack_bits(c, forceCheck, baseBitNew, baseAddressNew)
                    if nextFreeBit > baseBitNew and occupiesZeroBits:
                        occupiesZeroBits = False
                    baseBitNew, baseAddressNew = nextFreeBit, nextFreeAddress   # nextFreeAddress really addressOfNextFreeBit
                addressWidth = 1+nextFreeAddress-baseAddress    # If node occupies addresses 0 & 1 it's width is 2 (1+(1-0)).
                if addressWidth == 1:
                    if occupiesZeroBits:    
                        addressWidth = 0    # If node occupies zero bits, it occupies 0 addresses as well.
                    #    logger.debug('occupies Zero Bits, address width forced to 0.')
                    #else:
                    #    logger.debug('free address is 0, width is 1.')
                else:
                    if nextFreeBit == 0:
                        addressWidth -= 1   # If next free bit is first bit in address, it doesn't take up last address.
                    #    logger.debug('free bit is 0, width is -1.')
                    #else:
                    #    logger.debug('free bit is not 0, width is cool.')
        hatchNode.properties['address_width'] = addressWidth    # Set property.
        return addressWidth # Return property as a convenience. 

    if False:
        def pack_bits(self, hatchNode, forceCheck=False, nextFreeBit=0, addressWidth=0):
            """ Define method for packing bits in one place.
                Should be called within a for loop like this:
                    addressWidth, nextFreeBit = 0, 0
                    for c in hatchNode.childNodes:
                        nextFreeBit, addressWidth = self.pack_bits(c, forceCheck, nextFreeBit, addressWidth)
            """
            if self.get_packable(hatchNode, forceCheck)[0]:    # If child is packable, get next free bit.
                #logger.debug(str(hatchNode) + ' is packable...')
                childWidth = self._set_bit_width(hatchNode, forceCheck)
                nextFreeBit += childWidth
                if addressWidth == 0 and childWidth > 0:   # Must come before "if nextFreeBit > DATA_BUS_WIDTH:" if addressWidth is 0 and we are going to wrap.
                    addressWidth = 1    # If exists, then addressWidth should be 1, not 0.
                if nextFreeBit > DATA_BUS_WIDTH:    # Too wide, put child node in the next address & start bits at it's end.
                    nextFreeBit = childWidth    # No worries: all packable nodes have less than DATA_BUS_WIDTH bits.
                    addressWidth += 1   # No worries: all packable nodes fit into a single address.
            else:   # Child is not packable.
                #logger.debug(str(hatchNode) + ' not packable...')
                nextFreeBit = 0 # Start again at first bit in data bus.
                addressWidth += self._get_address_width(hatchNode, forceCheck)
            return nextFreeBit, addressWidth

    def pack_bits(self, hatchNode, forceCheck=False, baseBit=0, baseAddress=0):
        """ Define method for packing bits.

            baseBit and baseAddress are automatically checked and corrected. If the hatchNode 
            cannot be packed at the values that are passed in, it will be wrapped, meaning the 
            first bit and the next address will be returned.  (This function assumes that the 
            next address is always empty, checking this assumption should happen elsewhere.)

            Should be called within a for loop like this:
                baseBit, baseAddress = 0, 0
                for c in hatchNode.childNodes:
                    baseBit, baseAddress, nextFreeBit, nextFreeAddress = self.pack_bits(c, forceCheck, baseBit, baseAddress)
                    put()   # put node in memory
                    baseBit, baseAddress = nextFreeBit, nextFreeAddress

            The method for packing bits can be boiled down into four cases (provided we only 
            pass-in a non-zero baseBit if the previous bits in that address are already full.)

            1 the hatch node is packable and fits into the remaining bits of the address:
                baseBit and baseAddress are valid, return them with nextFreeBit and nextFreeAddress.
            2 the hatch node is packable but does not fit and must be wrapped:
              Return a baseBit of 0, baseAddr+1, and the next free bit & address.
            3 the hatch node is unpackable and baseBit != 0: (Previous bits in address are full.)
                Return baseBit of 0, baseAddr+1, and next free bit & address.
            4 hatch node is unpackable and baseBit == 0:
                baseBit and baseAddress are valid, return them with nextFreeBit and nextFreeAddress.
        """
        #logger.debug(self.pack_bits.func_name + "(" + hatchNodeClassAndName(hatchNode) + ")")
        nextFreeBit = baseBit
        nextFreeAddress = baseAddress
        if self.get_packable(hatchNode, forceCheck)[0]:    # Child is packable.
            #logger.debug(str(hatchNode) + ' is packable...')
            bitWidth = self._set_bit_width(hatchNode, forceCheck)    # Check if it fits.
            nextFreeBit = baseBit + bitWidth
            #logger.debug('occupies bits ' + str(baseBit) + ' to ' + str(nextFreeBit) + ' of ' + str(baseAddress))
            if nextFreeBit > DATA_BUS_WIDTH:    # Too wide, put child node in the next address & start bits at it's end.
                baseBit = 0 # Wrap to first bit of next address.
                baseAddress += 1   # Wrap to next address.
                nextFreeBit = bitWidth    # All packable nodes have less than DATA_BUS_WIDTH bits, so this is valid.
            #    logger.debug('wapping to ' + str(baseBit) + ' to ' + str(nextFreeBit) + ' of ' + str(baseAddress))
            #else:
            #    logger.debug('not wrapping')   # hatchNode fits as it is, do nothing.
            nextFreeAddress = baseAddress   # All packable nodes have less than DATA_BUS_WIDTH bits, so address is not full.
        else:   # Child is not packable.
            #logger.debug(str(hatchNode) + ' not packable...')
            if baseBit != 0:
                baseBit = 0 # Wrap to first bit of next address.
                baseAddress += 1   # Wrap to next address.
            #    logger.debug('wapping to ' + str(baseBit) + ' of ' + str(baseAddress))
            #else:
            #    logger.debug('not wrapping')   # hatchNode fits as it is, do nothing.
            nextFreeBit = 0    # Don't pack anything in after this node.
            nextFreeAddress = baseAddress + self._get_address_width(hatchNode, forceCheck, baseBit)
        #logger.debug('returning ' + str(baseBit) + ' of ' + str(baseAddress) + ' to ' + str(nextFreeBit) + ' of ' + str(nextFreeAddress))
        return baseBit, baseAddress, nextFreeBit, nextFreeAddress




#### TODO #################



class Hatch_Address_Mapper_Optimized(Hatch_Address_Mapper_Packed):
    """ Set the bit and address-related properties of a hatch node in an optimal way.
        Hatch nodes that take up more than one data bus address are placed into rounded address values for optimal address decoding.
        Smaller nodes are then placed into the available spaces inbetween large nodes.
        Also does bit-packing.
    """
#    def _set_bit_width(self, hatchNode, forceCheck=False):
#        pass
#    def _get_address_width(self, hatchNode, forceCheck=False):
#        pass
#    def set_local_map(self, hatchNode, baseAddress=0, baseBit=0):
#        pass
#    def set_global_map(self, hatchNode, baseAddress=0, baseBit=0):
#        pass


    def _get_address_width(self, hatchNode):
        """ Get the width in addresses of a hatch node.
            If the address width is not set, set it first.
        """
        addressWidth = 0
        try:
            addressWidth = hatchNode.properties['address_width']    # Already set.
        except KeyError, e:
            addressWidth = self.set_address_width(hatchNode)
        return addressWidth

    # XXX XXX XXX

    def set_address_width(self, hatchNode):
        """ Set the width in addresses of a hatch node.
            Address width is affected by how well a Struct or it's child 
            Structs' bits will be packed or arranged in memory.            
        """
        """
                # Get next power of 2 for easy address decoding (ex: 3->4, 5->8, 6->8, 14->16, etc.)
                shift = 0
                while (address_len >> shift) > 0:
                    shift += 1
                next_free_address = 1 << shift+1
        """       

        # TODO - NO PACKING DONE.
        addressWidth = 0
        if len(hatchNode.childNodes) == 0:
            addressWidth = 1    # Lowest-level node takes up < DATA_BUS_WIDTH bits and fits into a single address.
        else:
            for c in hatchNode.childNodes:
                addressWidth += self._get_address_width(c)
        hatchNode.properties['address_width'] = addressWidth
        return addressWidth # For convenience.

        if False:
            """
            # Round up to nearest power of 2 to optimize address decoding.
                    addressWidth = 0
                if self.is_packable(hatchNode):
                    addressWidth = 1    # A packable hatch node will always fit into a single address (bits < DATA_BUS_WIDTH & wrapping not allowed).
                    else:   # An unpackable node must be arranged in memory to see how well its contents will fit.
                        # XXX set these ?
                        hatchNode.properties['global_base_bit'] = 0 # Is not packable, must start on first bit of the address in data bus.
                        hatchNode.properties['local_base_bit'] = 0  # Is not packable, so parent is also not packable, and both must start on first bit of the address.

                        #addressWidth = self.arrange(hatchNode, globalBaseBit=0)    # bit-packing is only affected by start bit.
                        ##addressWidth = self.arrange(hatchNode, self._get_address_width, baseAddr, baseBit)
                        #if not hatchNode.properties['packed']: # TODO - implement packing.
                        #else:
                        next_free_address = 0
                        for c in hatchNode.childNodes:
                            _get_address_width

                        hatchNode.childNodes.reverse()    # Put last-added node in the Least-Significant-Bits.   XXX always ?

                    free_address = baseAddress
                    if not self.properties['packed']:  # Struct is not packed.
                        free_bit = 0    # Force base bit to zero for unpacked structs & their contents.
                        for c in self.childNodes:
                            free_address += callback(free_address, free_bit)    # Recurse into child if it is a Struct.
                    else:   # Struct is packed.
                        free_bit = baseBit
                        for c in self.childNodes:
                            if c.is_packable(): # Child is packable.
                                child_bit_width = c._set_bit_width() # Call this as child might be a Struct (new recurse into).
                                if free_bit + child_bit_width <= DATA_BUS_WIDTH: # Pack child IF it will fit.
                                    dummy = callback(free_address, free_bit)    # Recurse into child if it is a Struct.
                                    free_bit += child_bit_width # Increment to next free bit in address.
                                    # TODO - set c.'width' to free_bit-base_bit (like a register) ?
                                else:   # Is packable but won't fit, use next available address instead.
                                    free_bit = 0
                                    free_address += 1  # Put in next available address.
                                    free_address += callback(free_address, free_bit)    # Recurse into child if it is a Struct.
                            else:   # Child is not Packable, use next available address instead.
                                free_bit = 0
                                free_address += 1  # Put in next available address.
                                free_address += callback(free_address, free_bit)    # Recurse into child if it is a Struct.
                    self.childNodes.reverse()    # Un-reverse.
                    return free_address - baseAddress   # Return address width, or next free addess - base address.

                hatchNode.properties['address_width'] = addressWidth
                return addressWidth # For convenience.
                    """

    def pack_addresses(self, hatchNode):
        """ """
        pass

    def get_local_base_bit(self, hatchNode):
        """ Get the local base bit of a hatch node (relative to it's parent's base bit.)
        """
        raise NotImplementedError
    def set_local_base_bit(self, hatchNode):  # Packs bits if hatch node is packable. 
        """ Set the local base bit of a hatch node (relative to it's parent's base bit.)
        """
        raise NotImplementedError
    def get_local_address(self, hatchNode):
        """ """
        raise NotImplementedError
    def set_local_address(self, hatchNode):
        """ """
        raise NotImplementedError

    def get_global_base_bit(self, hatchNode):
        """ """
        baseBit = 0
        try:
            baseBit = hatchNode.properties['global_base_bit']    # Already set.
        except KeyError, e:
            baseBit = self.set_base_bit(hatchNode)
        return baseBit
    def set_global_base_bit(self, hatchNode):  # Packs bits if hatch node is packable.
        """ """
        raise NotImplementedError
    def get_global_address(self, hatchNode):
        """ """
        raise NotImplementedError
    def set_global_address(self, hatchNode, globalAddress=0):   # This should be the function that gets called externally. All others called internally.
        """ """
        if hatchNode.parent is not None:    # check for top node.
            raise AssertionError, "Global addresses can only be set from the top hatch node in a design."
        hatchNode.properties['global_address'] = globalAddress
        for c in hatchNode.childNodes:
            self.set_global_address(c, globalAddress)
            globalAddress += self._get_address_width(c)  # Set to next free address.



    ## XXX XXX XXX build functions

    def set_address_and_bit(self, hatchNode, baseAddr=0, baseBit=0):
        """ Set the local base address & local base bit of a hatch node.
            Also sets the address width & bit width properties.

            As a convenience, this function also returns the calculated 
            address width so that _get_address_width doesn't have to be called.

            By specifying a base address manually, we can throw an error later 
            if the program attempts to set a different base address.
        """
        if self.parent == None and baseAddr != 0:   # Assert the use case for this function.
            raise AssertionError, hatchNode.__class__.__name__ + " '" + hatchNode.name + "' is the top of the tree, so you should not be passing in a base address."

        if hatchNode.has_property('local_address'):
            oldBaseAddr = hatchNode.property('local_address') 
            if oldBaseAddr != 0:    # XXX Prevents setting of base address twice.  What if we need to call elaborate() twice... ?
                raise AssertionError, hatchNode.__class__.__name__ + " '" + hatchNode.name + "' already has a base address of " + str(hex(oldBaseAddr)) + "."
        # TODO - check that baseAddr isn't outside of a preset address width ?
        # TODO - check that we haven't passed a non-zero base_bit into a non-packable struct (this would cause address overlap.) ?

        # Errors raised by here.
        hatchNode.properties['local_address'] = baseAddr
        # hatchNode.set_property('base_bit', baseBit)

        # Arrange pieces in memory & calculate address width.
        address_width = self.arrange(self.set_address_and_bit, baseAddr, baseBit)
        # TODO - check that self.property('address_range') is big enough to address all registers in this struct. (It may have been manually specified.) ?
        self.properties['address_width'] = address_width
        return address_width


    # TODO - split into : pack_bits, pack_addresses
    def arrange(self, hatchNode, callback, baseAddress, baseBit):
        """ Make calls on this Struct and it's child nodes to see how they will
            arrange themselves in memory given the base address & base bit that 
            are passed in (and whether or not anything is packed.)

            This function returns the calculated address width as a convenience
            whether or not the property is saved.
            'callback' can be set to this function, or any other function that 
            calls this function & returns the returned value.

            There are two types of Structs:
            Structs that are not packed, and may not be packed into something else.
            Structs that are packed, and may be packed into something else (if they are 
            packable, so having a non-zero base bit like a Register should be possible.)
            This is not an optimal solution, but it makes for easier recursion.
        """
        # Set base address & base bit of contents.
        self.childNodes.reverse()    # Put last-added node in the Least-Significant-Bits.
        free_address = baseAddress
        if not self.properties['packed']:  # Struct is not packed.
            free_bit = 0    # Force base bit to zero for unpacked structs & their contents.
            for c in self.childNodes:
                free_address += callback(free_address, free_bit)    # Recurse into child if it is a Struct.
        else:   # Struct is packed.
            free_bit = baseBit
            for c in self.childNodes:
                if c.is_packable(): # Child is packable.
                    child_bit_width = c._set_bit_width() # Call this as child might be a Struct (new recurse into).
                    if free_bit + child_bit_width <= DATA_BUS_WIDTH: # Pack child IF it will fit.
                        dummy = callback(free_address, free_bit)    # Recurse into child if it is a Struct.
                        free_bit += child_bit_width # Increment to next free bit in address.
                        # TODO - set c.'width' to free_bit-base_bit (like a register) ?
                    else:   # Is packable but won't fit, use next available address instead.
                        free_bit = 0
                        free_address += 1  # Put in next available address.
                        free_address += callback(free_address, free_bit)    # Recurse into child if it is a Struct.
                else:   # Child is not Packable, use next available address instead.
                    free_bit = 0
                    free_address += 1  # Put in next available address.
                    free_address += callback(free_address, free_bit)    # Recurse into child if it is a Struct.
        self.childNodes.reverse()    # Un-reverse.
        return free_address - baseAddress   # Return address width, or next free addess - base address.


        def __set_address__ (self, baseAddr=0): # TODO - rename as *_set_width_*
            """ Set the address field of the data structure and return the number of bits now required for addressing.
                Also sets the addresses of childNodes & store the width of this struct.
            """
            self.set_property('hatch_address', baseAddr)    # Address set, now calculate the number of bits required to address this pack.
            bitBase = 0 # Accumulator
            self.childNodes.reverse()  # Reverse the content list so that the last register defined in a pack appears at the LSB's
            for c in self.childNodes:
                ## XXX XXX assumes c is a register.
                ignored_bits_reqd_to_address_c = c.__set_address__(baseAddr) # XXX no check: Won't recurse here as type(c) must be a Register.  Returned value is ignored.
                bitBase = c.bit_range(bitBase)  # Set c.bitbase, get c.bitbase+c.width back to use as new bitbase.
            self.childNodes.reverse()
            self.set_property('width', bitBase) # Store the final bit base as the width of this pack.
            return self.get_address_range(baseAddr) # Get bits required to address this struct.

    # These functions have all been moved into the hatch address mapper visitor class.
    if False:
        def _sort_block_list_by_size_(l):
            """ Go through the block list and sort them by size.
                Classic bubble sort.
            """
            for a in range(len(l) - 1):
                for b in range(len(l) - a - 1):
                    s1 = l[b][1]    # [1]
                    s2 = l[b+1][1]
                    if s2 > s1:
                        t = l[b+1]
                        l[b+1] = l[b]
                        l[b] = t
            return l

        def _sort_block_list_by_base_(l):
            """ Go through the blocks and sort them by base.
                Classic bubble sort.
            """
            for a in range(len(l) - 1):
                for b in range(len(l) - a - 1):
                    b1 = l[b][0]    # [0]
                    b2 = l[b+1][0]
                    if b2 > b1:
                        t = l[b+1]
                        l[b+1] = l[b]
                        l[b] = t
            return l

        def _build_free_block_list_(fixedBlockList):
            """ Build a list of free blocks from the list of blocks already
                alocated and locked down.
            """
            # copy the fixed block list.
            fbl = []
            for b in fixedBlockList:
                fbl.append(b)

            _free_block_list = []
            
            # if there is already stuff in the list, don't add the bottom of
            # memory, we only wnat to grow up from any predefined modules.
            if len(fbl) == 0:
                global BOTTOM_OF_MEMORY
                fbl.append([BOTTOM_OF_MEMORY,0, None])

            # add a fixed block at the top of memory
            global TOP_OF_MEMORY
            fbl.append([TOP_OF_MEMORY,0, None])
            # now go through the fixed blocks and sort them by base address
            _sort_block_list_by_base_(fbl)

            # now check that they do not overlap.
            for a in range(len(fbl) - 1):
                # base 1 is higer in memeory than base 2.
                b1 = fbl[a][0]
                r1 = fbl[a][1]
                b2 = fbl[a+1][0]
                r2 = fbl[a+1][1]
                if b1 > b2 and b1 < (b2 + r2) :
                    e = """*** ERROR - base address 0x%x of %s inside the address range of
                %s which goes from 0x%x to 0x%x."""%(b1, fbl[a][2].hatchling.name,
                                                     fbl[a+1][2].hatchling.name, b2, b2+r2)
                    raise e

            # now find any free space between blocks.
            for a in range(len(fbl) - 1):
                # base 1 is higer in memeory than base 2.
                b1 = fbl[a][0]
                r1 = fbl[a][1]
                b2 = fbl[a+1][0]
                r2 = fbl[a+1][1]
                # how big is the space between these two blocks?
                freeBase = b2 + r2
                freeRange = b1 - freeBase
                _free_block_list.append([freeBase, freeRange])
                # print "free space between 0x%x and 0x%x"%(freeBase, freeBase + freeRange)
            # now go through the free blocks and sort them by size
            _sort_block_list_by_size_(_free_block_list)
            # want the small free blocks at the top.
            _free_block_list.reverse()

            return _free_block_list

        def _get_base_addre_of_space_(_free_block_list, size):
            """ Find a space in the list of free block that is big enaugh to
                fit the block we have and return the base address of the location
                to use.
            """
            i = 0
            r = None
            decodeBits = int(math.ceil(math.log(size) / math.log(2)))
            while i < len(_free_block_list):
                b = _free_block_list[i][0] # base
                s = _free_block_list[i][1] # size
                if s >= size:
                    # make a "nice' decode.
                    addrRange = (2L ** decodeBits)
                    mask = addrRange - 1L
                    baseAddr = b
                    if (baseAddr & mask) != 0:
                        baseAddr = (baseAddr & mask) + addrRange
                    # check that it now fits.
                    if (baseAddr + addrRange) <= (b + s):
                        # it fits!
                        r = baseAddr
                        break
                    # it did not fit, so keep looking.
                i += 1
            if r == None:
                raise "*** Could not find free space for the movable block."
            return r










# Main for test
if __name__ == "__main__":

    consoleHandler.setLevel(logging.DEBUG)

    from hatch_nodes.hatch_node_physical import HatchNodePhysical
    h0 = HatchNodePhysical('h0', bit_width=20)
    h1 = HatchNodePhysical('h1', bit_width=11)
    h2 = HatchNodePhysical('h2', bit_width=02)
    h3 = HatchNodePhysical('h3', bit_width=03)
    h4 = HatchNodePhysical('h4', bit_width=24)
    h5 = HatchNodePhysical('h5', bit_width=1, packed=False)

    h0h1 = HatchNodePhysical('h0h1', h0, h1)
    h2h0h1 = HatchNodePhysical('h2h0h1', h2, h0h1)
    h4h3h2h0h1 = HatchNodePhysical('h4h3h2h0h1', h4, h3, h2h0h1)
    h5h4h3h2h0h1 = HatchNodePhysical('h5h4h3h2h0h1', h5, h4h3h2h0h1)
    hatchNodes = [h0, h1, h2, h3, h4, h5, h0h1, h2h0h1, h4h3h2h0h1, h5h4h3h2h0h1]

    if False:    # Normal address mapper.
        am = Hatch_Address_Mapper()
        for hatchNode in hatchNodes:
            #print str(hatchNode)
            #am._set_bit_width(hatchNode)
            #am._get_address_width(hatchNode)
            am.visit(hatchNode)
            print hatchNode.info()
            raw_input()

    elif True:    # Bit-packed address mapper.
        bp = Hatch_Address_Mapper_Packed()
        for hatchNode in hatchNodes:
            #print str(hatchNode)
            #print bp._set_bit_width(hatchNode, forceCheck=False)
            #print bp.get_packable(hatchNode, forceCheck=False)
            #print bp._get_address_width(hatchNode, forceCheck=False, baseBit=0)
            bp.visit(hatchNode)
            print hatchNode.info()
            raw_input()


